package leetcode_1100;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

public class _校园自行车分配 {
	public static void main(String[] args) {
		_校园自行车分配 test = new _校园自行车分配();
		int res[] = test.assignBikes(new int[][] {new int[] {0,0},new int[] {2,1}}, 
				new int[][] {new int[] {1,2},new int[] {3,3}});
	}
	
	class Distance {
		int worker;
		int bike;
		int val;
		public Distance(int worker,int bike,int val) {
			this.worker = worker;
			this.bike = bike;
			this.val = val;
		}
	}
	
	public int[] assignBikes(int[][] workers, int[][] bikes) {
        PriorityQueue<Distance> queue = new PriorityQueue<>(new Comparator<Distance>() {

			@Override
			public int compare(Distance o1, Distance o2) {
				if(o1.val == o2.val) {
					if(o1.worker == o2.worker)
						return o1.bike - o2.bike;
					return o1.worker-o2.worker;
				}
				return o1.val - o2.val;
			}
		});
        int res[] = new int[workers.length];
        for(int i=0;i<workers.length;++i) {
        	for(int j=0;j<bikes.length;++j) {
        		int dis = Math.abs(workers[i][0]-bikes[j][0])+Math.abs(workers[i][1]-bikes[j][1]);
        		Distance now = new Distance(i, j, dis);
        		queue.offer(now);
        	}
        }
        HashSet<Integer> w = new HashSet<Integer>();
        HashSet<Integer> b = new HashSet<Integer>();
        while(!queue.isEmpty()) {
        	Distance now = queue.poll();
        	if(!w.contains(now.worker)&&!b.contains(now.bike)) {
        		res[now.worker] = now.bike;
        		w.add(now.worker);
        		b.add(now.bike);
        	}
        }
        return res;
    }
}
